package 中等.搜索.深度优先搜索;

import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
 * 返回包含原始树中所有 最深节点 的 最小子树 。
 * 如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
 * 一个节点的 子树 是该节点加上它的所有后代的集合。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes
 */
public class 具有所有最深节点的最小子树_865 {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;

        new 具有所有最深节点的最小子树_865().subtreeWithAllDeepest(node1);

    }

    private int maxLevel;

    private List<List<TreeNode>> lists = new ArrayList<>();

    /**
     * 深度搜索的过程记录从根节点到叶子节点的路径
     * 每个最深的节点都有一条路径，求构成的最小树
     * 那么从后往前遍历，如果在某相同层位置存在相同
     * 的节点，即为包含所有最深节点的最小树根节点
     */
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        dfs(root, new ArrayList<>());

        for (int i = maxLevel - 1; i >= 0; i--) {
            boolean flag = true;
            for (int j = 1; j < lists.size(); j++) {
                if (lists.get(j).get(i) != lists.get(j - 1).get(i)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return lists.get(0).get(i);
            }
        }

        return root;
    }

    private void dfs(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        if (list.size() > maxLevel) {
            lists = new ArrayList<>();
            maxLevel = list.size();

            lists.add(list);
        } else if (list.size() == maxLevel) {
            lists.add(list);
        }

        dfs(root.left, new ArrayList<>(list));
        dfs(root.right, new ArrayList<>(list));
    }

}
